COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	hender[e86,jmc]	Notes on Peter Henderson: Functional Programming] re: CS306
C00008 ENDMK
C⊗;
hender[e86,jmc]	Notes on Peter Henderson: Functional Programming] re: CS306

There are lots of good examples:

	We need especially to see if there are really good examples
of the use of functions with functions as output.

	It may be worthwhile to use his problems of dimensional
analysis, graph search and singletons.  In the graph search, using gopher
or the abstract cdr may help a lot. Virtual lists - abstract lists.
Likewise in singletons.  Have I seen this before?  Refer to Knuth.
Have I seen something similar before?

Henderson remarks early that the increase in computer speed means
that less efficient methods may be used in order to achieve
more transparent programs.  At least in that section, he doesn't
face the possibility that the more transparent may be less efficient
by a data dependent amount that grows too fast with the data.
However, without relating it to this issue he does discuss the
elimination of the use of append in reverse and the avoidance of
exponential growth in certain problems.

Using multiple output functions, we have

singletons[x,ones,mores] ← if at x then
	[if x ε mores then ones,mores
	else if x ε ones then delete[x,ones],x.mores
	else x.ones,mores]
else singletons[d x,singletons[a x,ones,mores]]

For efficiency we need efficient ways of testing membership of atoms
in a set, getting the result of deleting and atom from a set and
adding an atom to a set.

	If we don't use multiple output functions we can write

(defun sing1 (x pr)
       (if (atom x)
	   (cond ((member x (cdr prs)) prs)
		 ((member x (car prs) (cons (delete x (car prs)) (cons x (cdr prs)))))
		 (t (cons (cons x (car prs)) (cdr prs))))
	   (sing1 (cdr x) (sing1 (car x) prs))))

Henderson defines essentially this function but the goes on to remark that
the use of the element  mores  only requires the ability to add to a set
and test membership, i.e. does not require deletion. (remove he calls it).
This induces him to represent sets by functions.  Deletion offers no more
difficulties conceptually, but since we don't know till we read
later chapters how he intends to implement it, the separation may be
worthwhile.  He offers the additional reason that our answer is going
to be the variable  ones, so we aren't so free to change its form.

Here's a version that only uses adding to list.

(defun singletons (x)
       (let ((w (sing2 x '(nil))))
	    (difference (car w) (cdr w))))

(defun sing2 (x alls_mores)
       (if (atom x)
	   (if (member x (car alls_mores))
	       (if (member x (cdr alls_mores))
		   alls_mores
		   (cons (car alls_mores) (cons x (cdr alls_mores))))
	       (cons (cons x (car alls_mores)) (cdr alls_mores)))
	   (sing2 (cdr x) (sing2 (car x) alls_mores))))

****

We need a heavy duty LISP.  It should contain functions that use sophisticated
ways of making certain kinds of efficient programming easy.  For example, it
should contain functions that use techniques described in Knuth's
Art of Computer Programming to handle sets where the operations are
adding an element, testing membership, and deleting an element.
This package may be distinct from a package that includes union and
intersection, because if the latter operations are not required, the
former group may be done more efficiently.  A package with the expanded
set of operations may be also included in heavy duty LISP.

The key issue is that of how many different ways of doing things need
to be provided.  Clearly, abstraction will help keep things in order.

We can include heavy duty LISP in Qlisp.

****

Apropos of p. 96. There is always a semantics of initial segments of
any language with a semantics - or even central segments.

What Henderson calls the abstract form of a program
is just another concrete syntax.